package cn.com.guage.dtm.leetcode.hot100;

import java.util.*;
import java.util.stream.Collectors;

/**
 * 给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
 * 字母异位词 是由重新排列源单词的所有字母得到的一个新单词。
 */
public class LeetCode_49_字母异位词分组 {
    public static void main(String[] args) {
        String[] arry = {"eat","tea", "tan", "ate", "nat", "bat"};
        groupAnagrams3(arry);
    }

    /**
     * 1. 利用了HashSet来保存单词排序后的key
     * 2.  两次循环，效率太低
     * @param strs
     * @return
     */
    public static List<List<String>> groupAnagrams(String[] strs) {
        int len = strs.length;
        List<List<String>> ans = new ArrayList<List<String>>();
        Set<String> set = new HashSet<String>();
        for (int i= 0; i < len; i++){
            char[] keyArray = strs[i].toCharArray();
            Arrays.sort(keyArray);
            set.add(String.valueOf(keyArray));
        }
        Iterator<String> iterable =  set.iterator();
        while (iterable.hasNext()){
            String key = (String) iterable.next();
           // System.out.println(key);
            List<String> list = new ArrayList<>();
            for (int j = 0 ; j < len; j++){
               char[] otherWorld = strs[j].toCharArray();
               Arrays.sort(otherWorld);
                if (key.equals(String.valueOf(otherWorld))){
                    list.add(strs[j]);
                }
            }
            ans.add(list);
        }
        System.out.println(ans);
       return ans;
    }

    /**
     * 效率太低 测试案例通过率只有80%
     * @param strs
     * @return
     */
    public static List<List<String>> groupAnagrams2(String[] strs) {
        int len = strs.length;
        List<List<String>> ans = new ArrayList<List<String>>();
        Set<String> set = new HashSet<String>();
        for (int i= 0; i < len; i++){
            char[] keyArray = strs[i].toCharArray();
            Arrays.sort(keyArray);
            //set不含有key时就可以遍历获取该key所有的异位词
            if (!set.contains(String.valueOf(keyArray))){
                List<String> list = new ArrayList<>();
                for (int j = 0 ; j < len; j++){
                    char[] otherWorld = strs[j].toCharArray();
                    Arrays.sort(otherWorld);
                    if (String.valueOf(keyArray).equals(String.valueOf(otherWorld))){
                        list.add(strs[j]);
                    }
                }
                ans.add(list);
            }
            //这一步非常重要，将已经提取到的第i项异位词添加到set集合,那么久防止后期重复遍历
            set.add(String.valueOf(keyArray));
        }
        System.out.println(ans);
        return ans;
    }

    /**
     * V getOrDefault(Object key, V defaultValue) 如果 Map 中不存在指定的键时，返回的默认值。
     * @param strs
     * @return
     */
    public static List<List<String>> groupAnagrams3(String[] strs) {
        List<List<String>> result = new ArrayList<>();
        Map<String, List<String>> map = new HashMap<String, List<String>>();
        for (String str : strs) {
            char[] array = str.toCharArray();
            Arrays.sort(array);
            String key = new String(array);
            List<String> list = map.getOrDefault(key, new ArrayList<String>());
            list.add(str);
            map.put(key, list);
        }
        result.addAll(map.values());
        return result;
    }

    public List<List<String>> groupAnagrams4(String[] strs) {
        return new ArrayList<>(Arrays.stream(strs)
                .collect(Collectors.groupingBy(str -> {
                    // 返回 str 排序后的结果。
                    // 按排序后的结果来grouping by，算子类似于 sql 里的 group by。
                    char[] array = str.toCharArray();
                    Arrays.sort(array);
                    return new String(array);
                })).values());
    }

}
